Graphs are useful for modeling many real world systems such as highway systems, telephone networks, and the World Wide Web. For example, a graph representing a highway system might be used to determine the shortest distance between an origin and a planned destination. A graph may also be used to represent the relationships between Internet web pages where nodes represent individual web pages and edges represent links between web pages. In general, graphs typically comprise multiple nodes or vertices connected to one another by one or more edges. Such graphs may be directed or undirected, and there may be a weight, a length/distance, or a cost associated with one or more edges.
In modeling real world abstractions, graphs can be used to measure the relatedness between two nodes. Depending on the model, the relatedness can be measured several different ways. One measure of relatedness may be the shortest path distance between two nodes in the graph. Another measure of relatedness may be the number of paths (presumably of a certain length) between a pair of nodes. However, as the number of nodes and edges in a graph grows, the average time and computing resources needed to calculate the relatedness between two nodes can become enormous and become problematic when computational resources are limited and/or near-instantaneous or real-time results are desirable or expected.
Social networks are one instance of a real world abstraction that can be readily modeled with a very large graph. In such a model, people in the social network can be represented as a set of nodes and relationships can be represented as the edges between the nodes. In some implementation, each edge may be weighted to reflect the degree of direct relatedness between each node, while the sum of weights of intervening edges can be used to reflect the degree of indirect relatedness between any two nodes not directly connected. However, with the immense size of Internet-based social networks—having tens of millions of nodes connected by varying degrees of separation—it has become increasingly difficult to determine the relatedness between persons as represented by, say, determining the shortest path between two nodes. This is particularly problematic in situations where real-time computations are required or computational resources are limited or both.